#include <stdio.h>
#include <malloc.h>

typedef struct TreeNode{
    char data;
    struct TreeNode * left, * right, * parent;
    // 0表示孩子，1表示线索
    int leftTag, rightTag;
}* ClueTree;

// 始终指向刚刚访问过的结点
ClueTree pre = NULL;

// 前序线索化
void preOrder(ClueTree root) {
    if(root) {
        if(root->left == NULL) {
            root->left = pre;
            root->leftTag = 1;
        }
        if(pre && pre->right == NULL) {
            pre->right = root;
            pre->rightTag = 1;
        }
        pre = root;
        if(root->leftTag == 0) {
            preOrder(root->left);
        }
        if(root->rightTag == 0) {
            preOrder(root->right);
        }
    }
}

void preTraverse(ClueTree root) {
    while (root) {
        printf("%c", root->data);
        // 左边是孩子，先走左边
        if(root->leftTag == 0) {
            root = root->left;
        } else{
            // 左边不是孩子，无论右边是线索还是孩子都要走了
            root = root->right;
        }
    }
}

// 中序线索化
void inOrder(ClueTree root) {
    if(root) {
        // 递归左孩子
        inOrder(root->left);
        // 没有左孩子时
        if(root->left == NULL) {
            // 前驱线索
            root->left = pre;
            root->leftTag = 1;
        }
        // 没有右孩子时
        if(pre->right == NULL) {
            // 后继线索
            pre->right = root;
            pre->rightTag = 1;
        }
        // 记录刚访问的结点
        pre = root;
        // 递归右孩子
        inOrder(root->right);
    }
}

// 中序线索后遍历
void inTraverse(ClueTree root) {
    while (root) {
        // 中序遍历需先去到最左边，若是非线索则持续往左边走
        while (root && root->leftTag == 0) {
            root = root->left;
        }
        // 去到最左边，打印中序遍历第一个结点
        printf("%c", root->data);
        // 有后继线索，沿着线索往后即可
        while(root && root->rightTag == 1) {
            root = root->right;
            printf("%c", root->data);
        }
        // 否则继续正常处理右孩子
        root = root->right;
    }
}

void postOrder(ClueTree root) {
    if(root) {
        postOrder(root->left);
        postOrder(root->right);
        if(root->left == NULL) {
            root->left = pre;
            root->leftTag = 1;
        }
        if(pre->right == NULL) {
            pre->right = root;
            pre->rightTag = 1;
        }
        pre = root;
    }
}

void postTraverse(ClueTree root) {
    // 记录上一个访问节点和当前节点
    ClueTree lastNode = NULL;
    ClueTree currentNode = root;
    while (currentNode) {
        // 一直往最左边走
        while (currentNode->left != lastNode && currentNode->leftTag == 0) {
            currentNode =  currentNode->left;
        }
        // 往右若有线索则跟随线索一直走
        while (currentNode && currentNode->rightTag  == 1) {
            printf("%c",  currentNode->data);
            lastNode = currentNode;
            currentNode = currentNode->right;
        }
        // 上面情况（左右节点情况已结束），此时需要处理的是兄弟节点
        // 特殊情况处理：若此时的节点就是根节点且其右孩子也已经被访问过，说明此时就是最后一个节点了
        if (currentNode == root && currentNode->right == lastNode) {
            printf("%c", currentNode->data);
            return;
        }
        // 若不是特殊情况，则表示需要通过父节点寻找兄弟节点了
        while(currentNode && currentNode->right == lastNode) {
            printf("%c", currentNode->data);
            lastNode = currentNode;
            currentNode =  currentNode->parent;
        }
        // 若右边不是线索，则直接往右找孩子，若是线索则等下一轮循环解决
        if(currentNode && currentNode->rightTag == 0) {
            currentNode = currentNode->right;
        }
    }
}

// 创建结点
ClueTree createNode(char data) {
    ClueTree newNode = malloc(sizeof(struct TreeNode));
    newNode->left = newNode->right = NULL;
    newNode->leftTag = newNode->rightTag = 0;
    newNode->data = data;
    return newNode;
}


int main() {
    ClueTree a = createNode('A');
    ClueTree b = createNode('B');
    ClueTree c = createNode('C');
    ClueTree d = createNode('D');
    ClueTree e = createNode('E');

    a->left = b;
    b->left = d;
    a->right = c;
    b->right = e;
    preOrder(a);
    a;
}